1. Technical Field
This invention relates to a system and method for providing real-time response in a read-copy-update (RCU) locking mechanism in a multiprocessor computer system.
2. Description of the Prior Art
Read-copy-update (RCU) is a mechanism that defers destruction of elements removed from a protected data structure, or a similar data organization element, until a concurrently executing read-only access to the data structure has completed an ongoing traversal of that data structure. The process for deferment of destruction of elements removed from the data structure permits lock free read-only access without incurring memory corruption and invalid pointer failures.
FIG. 1 is a prior art diagram (5) illustrating the RCU mechanism for removing an element from a data structure. In this example, element B (14) is being deleted from a data structure that contains elements A (10), B (14), and C (18), in that order. Initially, Step0, the data structure is linked such that element A (10) includes a first pointer (12) to element B (14), and element B (14) includes a second pointer (16) to element C (18). The first step, Step1, in removing element B (14) from the data structure using the RCU mechanism, is to move the first pointer (12) that originally extended from element A (10) to element B (12) to extend from element A (10) to element C (18). In FIG. 1, the movement of the first pointer (12) is shown as a third pointer (20). However, technically, the third pointer (20) is the same as the first pointer (12) but referencing a different element in the data structure. Pointers (12) and (20) cannot be present at the same time, however, readers currently referencing element C (18) may have arrived at element C (18) either using the old value (12) or the new value (20) of the pointer. Therefore, old value(12) and new value (20) represent different values for the same pointer. Any readers traversing this data structure concurrently with the deletion at Step1 continue to be directed to either element B (14) or element C (18) in the data structure. Once a grace period has elapsed, there will not be any readers referencing element B (14) since the path provided in Step0 by the first pointer (12) to element B (14) has been removed, as shown in Step2. Following the grace period, element B (14) may now be freed from memory, as shown in Step3. In this way, RCU defers freeing of elements removed from an RCU protected data structure until concurrently executing read actions have completed any ongoing traversals of that data structure.
The current implementation of the Linux 2.6 kernel provides two primitives that determine how long element B (14), from FIG. 1, must be retained in the data structure prior to removal therefrom. One of the primitives is known as synchronize_kernel, which cannot be called from an interrupt handler or within a spin lock. The synchronize_kernel primitive blocks a caller's subsequent execution by waiting until the end of a subsequent grace period, i.e. until current readers accessing data structure have completed that traversal. FIG. 2 is a flow chart (30) of a prior art use of this synchronize_kernel primitive showing removal of an element from a data structure and freeing the element from memory. The first step involves removal of an element from the data structure (32). Following removal of the element, the synchronize_kernel primitive is invoked in order to wait for one grace period to elapse (34). Once the grace period elapses (36), the synchronize_kernel primitive returns to its caller. This caller can then free (38) the element designated for removal from the data structure at step (32). Accordingly, the synchronize_kernel primitive is one mechanism for efficient access by readers to the data structure.
The second primitive provided by the Linux 2.6 kernel is the call_rcu primitive. This primitive supports efficient removal of an element from a data structure without requiring a context switch, wherein a context switch supports changing among concurrently operating processes in a multitasking environment. The call_rcu primitive registers the function that is freeing the element designated for removal from the data structure. FIG. 3 is a flow chart (40) of a prior art use of the call_rcu primitive for removal of an element from a data structure and freeing the element from memory. The first step involves removal of an element from the data structure (42). Following removal of the element at step (42), the element is then scheduled for removal from memory following a grace period through use of the call_rcu primitive (44). The call_rcu primitive places the element designated for removal from the data structure into a queue for removal at a later time (46). Following elapse of a grace period (48), the element in the queue is freed from memory (50). Accordingly, the call_rcu primitive is another mechanism for efficient removal of an element from a data structure and memory.
Current implementation of Linux 2.6 kernel has the effect of taking all of the elements scheduled to be removed during a specified period and executing removal of all of the elements at the end of a subsequent grace period. In addition, the implementation does not limit the number of elements that may be removed during a given grace period. By executing removal of a batch of designated elements at the end of a subsequent grace period, real-time performance associated with the removal is not provided as the current implementation imposes an arbitrary scheduling latency. Therefore, there is a need for modifying the implementation of both call_rcu and synchronize_kernel primitives in the Linux 2.6 kernel or equivalent module of an operating system to mitigate latency and provide real-time, i.e. immediate application for removal of designated elements from memory.